package org.jikeshijian;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 * @Auther: qingle
 * @Date: 2024/9/10-5:56
 * @Description:
 * @version: 1.0
 */
public class Solution {
		public int[] maxSlidingWindow(int[] nums, int k) {
			if (nums == null || k <= 0) return new int[0];
			int n = nums.length;
			int[] res = new int[n - k + 1];
			Deque<Integer> deque = new ArrayDeque<>();

			for (int i = 0; i < n; i++) {
				// 移除不在窗口内的元素索引
				while (!deque.isEmpty() && deque.peek() < i - k + 1) {
					deque.poll();
				}
				// 移除所有小于当前元素的索引，保持队列单调递减
				while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
					deque.pollLast();
				}
				deque.offer(i);
				// 每个窗口的开始处记录最大值
				if (i >= k - 1) {
					res[i - k + 1] = nums[deque.peek()];
				}
			}
			return res;
		}

	public int[] maxSlidingWindow2(int[] nums, int k) {
		if (nums == null || k <= 0) return new int[0];
		int n = nums.length;
		int[] res = new int[n - k + 1];
		PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

		for (int i = 0; i < n; i++) {
			// 维护堆的大小不超过k，并且移除不在窗口内的元素索引
			if (i >= k && heap.size() > 0 && heap.peek()[1] <= i - k) {
				heap.poll();
			}
			heap.offer(new int[]{nums[i], i});
			if (i >= k - 1) {
				res[i - k + 1] = heap.peek()[0];
			}
		}
		return res;
	}

	public int[] maxSlidingWindow3(int[] nums, int k) {
		if (nums == null || k <= 0) return new int[0];
		int n = nums.length;
		int[] res = new int[n - k + 1];
		PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> nums[b] - nums[a]);

		for (int i = 0; i < n; i++) {
			// 维护优先队列的大小不超过k
			if (i >= k) pq.remove(nums[i - k]);
			pq.offer(i);
			if (i >= k - 1) {
				res[i - k + 1] = nums[pq.peek()];
			}
		}
		return res;
	}

	public static void main(String[] args) {
		final int length = 100000;
		final int k = 300; // 窗口大小
		int[] nums = new int[length];
		for (int i = 0; i < length; i++) {
			nums[i] = (int) (Math.random() * 1000); // 生成随机数填充数组
		}


		// 测试双端队列方法
		long startTime = System.nanoTime();
		Solution solutionDeque = new Solution();
		int[] resultDeque = solutionDeque.maxSlidingWindow(nums, k);
		long endTime = System.nanoTime();
		System.out.println("Deque Time: " + (endTime - startTime) + " ns");

		// 测试优先队列方法
		startTime = System.nanoTime();
		Solution solutionPriorityQueue = new Solution();
		int[] resultPriorityQueue = solutionPriorityQueue.maxSlidingWindow3(nums, k);
		endTime = System.nanoTime();
		System.out.println("Priority Queue Time: " + (endTime - startTime) + " ns");

		// 测试小顶堆方法
		startTime = System.nanoTime();
		Solution solutionMinHeap = new Solution();
		int[] resultMinHeap = solutionMinHeap.maxSlidingWindow2(nums, k);
		endTime = System.nanoTime();
		System.out.println("Min Heap Time: " + (endTime - startTime) + " ns");
	}

}
